In symmetric cryptography, the sender and the recipient of a message share the knowledge of one and the same secret key K. The latter allows the sender to transform the plaintext message into a cryptogram, or encrypted message, and the recipient to recover the plaintext message from the encrypted message.
The invention is concerned more particularly with probabilistic schemes for symmetric encryption. An encryption scheme is termed “probabilistic” when it involves a random item in the encryption. It follows from this that, if the same plain message is encrypted twice, two different encrypted messages are obtained with a high probability. Indeed, the encrypted message depends not only on the plaintext message but also on the random item. Probabilistic encryption schemes contrast with deterministic encryption schemes which always provide the same encrypt for a given plain message and a given key.
A typical example of a probabilistic symmetric encryption scheme is an encryption scheme using a block encryption algorithm, such as AES (Advanced Encryption Standard) or DES (Data Encryption Standard), combined with a CBC (Cipher Block Chaining) operative mode. By definition, an “operative mode”, or “mode of operation”, is the way of processing the plain and encrypted text blocks within a block encryption algorithm. In the CBC mode, the plain text is cut up into blocks M1|M2| . . . |Mn and the encrypt C0|C1|C2| . . . |Cn is defined by Ci=Ek(Mi+Ci-1) with C0=IV, where IV (Initialization Vector) is a random block which gives the encryption its probabilistic character. Several other operative modes, appropriate for probabilistic symmetric encryption, exist: CFB (Cipher Feedback), OFB (Output Feedback), CTR (Counter), etc.
Thus, most symmetric encryption schemes use a block encryption algorithm with a certain operative mode. The security of such encryption schemes is analyzed in two stages:                initially, the security of the block encryption algorithm is analyzed by studying its behavior in the guise of pseudo-random permutation, the aim being to verify that a permutation generated by the block encryption and associated with a random key is not distinguishable from a perfectly random permutation,        subsequently, the security of the operative mode is analyzed by assuming that the block encryption is a perfectly safe pseudo-random permutation.        
In general, the security of the operative mode can be proved in a rigorous manner. By way of examples, the CTR and CBC operative modes are proved safe in the sense that it is possible to demonstrate that they are unbreakable when the block encryption used is itself unbreakable.
On the other hand, it is trickier to prove the security of the block encryption algorithm.
In a general way, there exist two concepts, well known to the person skilled in the art, characterizing the security of a cryptographic system:                unconditional security and        computational security.        
By definition, an algorithm is unconditionally safe if an attacker cannot recover any information about the plain text from the encrypted text, whatever the computational power thereof.
In the symmetric field, only unconditional security can be proved. It follows from this that the security of the known encryption algorithms is currently based on empirical foundations. Mathematical arguments for determining a lower bound relating to the complexity of attacks are not available for any known block encryption algorithm. The current arguments regarding the security of block encryption algorithms are essentially the following:                absence of known attacks of lower complexity than the desired security level;        provable resistance to particular attack schemes, for example resistance to differential cryptanalysis and to linear cryptanalysis;        in the case of certain algorithms such as DES, existence of proofs of resistance to attacks in the so-called Luby and Rackoff security model in which certain components of the real algorithm are replaced with perfectly random ideal functions.        
Currently, none of the known schemes for probabilistic symmetric encryption using a block encryption algorithm and an operative mode reconciles the following two requirements:                the existence of mathematical arguments for buttressing the computational security of the encryption and thus proving that an attacker able to acquire a polynomial number of plain/encrypted pairs cannot deduce from an additional encrypt any information about the corresponding plain text;        the existence of software means for implementing the encryption scheme the speed of which is close to that of the block algorithms currently used, such as AES and DES, and requiring realistic computational resources.        
There therefore exists a requirement for a probabilistic symmetric encryption scheme for which it is possible to prove security by a reductionist approach consisting in translating security into an assumption about the difficulty of solving a known problem. If this assumption is satisfied, then the scheme is safe. Stated otherwise, there exists a requirement for a probabilistic symmetric encryption scheme for which it is possible to prove that, in order to break the security of this encryption scheme, an attacker must be capable of solving a known, presumed difficult problem.